import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 155. Min Stack 最小栈
 * https://leetcode.com/problems/min-stack/
 */

/**
 * 方法：使用双端队列实现最小栈，每个元素存储当前值和当前最小值
 * 
 * Args:
 *   val: 要入栈的整数值
 * 
 * Returns:
 *   push: 无返回值
 *   pop: 无返回值
 *   top: 返回栈顶元素的值
 *   getMin: 返回当前栈中的最小值
 * 
 * Time:
 *   push: O(1)
 *   pop: O(1)
 *   top: O(1)
 *   getMin: O(1)
 * 
 * Space: O(n) - 需要存储所有元素及其对应的最小值
 */
class MinStack {
    // 注意不要使用 Stack 类，因为它继承自 Vector，是同步的，会导致一些性能问题
    private final Deque<int[]> st = new ArrayDeque<>();

    public MinStack() {
        // 添加栈底哨兵 Integer.MAX_VALUE
        // 这里的 0 写成任意数都可以，反正用不到
        st.push(new int[]{0, Integer.MAX_VALUE});
    }
    
    public void push(int val) {
        st.push(new int[]{val, Math.min(getMin(), val)});
    }
    
    public void pop() {
        st.pop();
    }
    
    public int top() {
        return st.peek()[0];
    }
    
    public int getMin() {
        return st.peek()[1];
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */